0% completed
Problem Statement
You are given a string called preorder that represents the serialization of a binary tree.
This serialization string is created using a preorder traversal, where each node's value is recorded if it is a non-null node. Otherwise, we record using a sentinel value such as '#'.
The string preorder contains only integers and the character '#', separated by commas. The format is always valid, so there will be no cases like two consecutive commas (e.g., "1,,4").
Return true, if this string is a valid serialization of a binary tree. Otherwise, return false.
Note: Note: You are not allowed to reconstruct the tree.
Examples
- Example 1:
- Input:
"5,2,#,#,3,1,#,#,#" - Expected Output:
true - Justification: The preorder traversal
"5,2,#,#,3,1,#,#,#"represents a valid binary tree. It can be visualized as:
- Input:
5
/
2
\
3
/
1
- Example 2:
- Input:
"7,3,1,#,#,4,#,#,8,#,2,#,#" - Expected Output:
true - Justification: The serialization
"7,3,1,#,#,4,#,#,8,#,2,#,#"corresponds to a valid binary tree:
- Input:
7
/ \
3 1
/
4
\
8
\
2
- Example 3:
- Input:
"1,#,#,2" - Expected Output:
false - Justification: The serialization
"1,#,#,2"cannot represent a valid binary tree. After the node1and its twonullchildren, there should not be any additional nodes left, but2appears, which violates the preorder traversal structure.
- Input:
Solution
To solve this problem, we start by recognizing that every non-null node in a binary tree requires a slot and provides two additional slots for its children. Meanwhile, a null node ('#') occupies a slot without adding any new slots. We initialize our available slots to 1 for the root node. As we traverse through the preorder string, each comma indicates the end of a node description. We decrement the available slots by one for every node processed. If the processed node is non-null, we add two more slots (since it provides room for two children); if it's null, we simply continue. The algorithm checks whether all slots are used up correctly by the end of the string.
The approach is efficient because it ensures a linear traversal through the input, checking at each step whether any inconsistencies exist in the structure of the binary tree. By the end of the string, if the slots available are exactly zero, then the preorder string is a valid serialization of a binary tree. Otherwise, it is not. This method allows us to validate the input without reconstructing the tree, keeping the solution optimal in both time and space complexity.
Step-by-Step Algorithm
- Initialize a variable
availableSlotsto1. This represents the initial slot required for the root node. - Calculate the length of the input string
preorderand store it in the variablelength. - Loop through each character in the
preorderstring from the first to the second last character:- Check if the current character is a comma (
,):- If true, decrement
availableSlotsby 1, since processing a node consumes one slot. - Check if
availableSlotsis less than 0:- If true, return
falseimmediately since there are not enough slots for the upcoming nodes.
- If true, return
- If the previous character is not
'#', incrementavailableSlotsby 2, indicating that a non-null node was processed, which creates two more slots for its children.
- If true, decrement
- Check if the current character is a comma (
- Process the last node:
- If the last character of
preorderis'#', decrementavailableSlotsby 1 since it consumes one slot. - If the last character is not
'#', incrementavailableSlotsby 1. Here, the last non-null node adds2slots and consumes1slot. So, we are adding remaining1slot only.
- If the last character of
- Check the final count of
availableSlots:- If
availableSlotsis 0, returntrue, indicating a valid serialization. - Otherwise, return
false.
- If
Algorithm Walkthrough
Let's walk through the input "5,2,#,#,3,1,#,#,#" step-by-step:
- Initialize
availableSlots = 1. - Calculate
length = 17(length of the input string). - Start loop with
i = 0toi = 16(excluding the last character for separate processing):- i = 0:
preorder.charAt(0) = '5', not a comma, continue to the next character. - i = 1:
preorder.charAt(1) = ',', a comma is found.- Decrement
availableSlotsby 1:availableSlots = 0. - Check the previous character
preorder.charAt(0) = '5', which is not'#'. - Increment
availableSlotsby 2:availableSlots = 2.
- Decrement
- i = 2:
preorder.charAt(2) = '2', not a comma, continue to the next character. - i = 3:
preorder.charAt(3) = ',', a comma is found.- Decrement
availableSlotsby 1:availableSlots = 1. - Check the previous character
preorder.charAt(2) = '2', which is not'#'. - Increment
availableSlotsby 2:availableSlots = 3.
- Decrement
- i = 4:
preorder.charAt(4) = '#', not a comma, continue to the next character. - i = 5:
preorder.charAt(5) = ',', a comma is found.- Decrement
availableSlotsby 1:availableSlots = 2. - Check the previous character
preorder.charAt(4) = '#', which is'#', no new slots created.
- Decrement
- i = 6:
preorder.charAt(6) = '#', not a comma, continue to the next character. - i = 7:
preorder.charAt(7) = ',', a comma is found.- Decrement
availableSlotsby 1:availableSlots = 1. - Check the previous character
preorder.charAt(6) = '#', which is'#', no new slots created.
- Decrement
- i = 8:
preorder.charAt(8) = '3', not a comma, continue to the next character. - i = 9:
preorder.charAt(9) = ',', a comma is found.- Decrement
availableSlotsby 1:availableSlots = 0. - Check the previous character
preorder.charAt(8) = '3', which is not'#'. - Increment
availableSlotsby 2:availableSlots = 2.
- Decrement
- i = 10:
preorder.charAt(10) = '1', not a comma, continue to the next character. - i = 11:
preorder.charAt(11) = ',', a comma is found.- Decrement
availableSlotsby 1:availableSlots = 1. - Check the previous character
preorder.charAt(10) = '1', which is not'#'. - Increment
availableSlotsby 2:availableSlots = 3.
- Decrement
- i = 12:
preorder.charAt(12) = '#', not a comma, continue to the next character. - i = 13:
preorder.charAt(13) = ',', a comma is found.- Decrement
availableSlotsby 1:availableSlots = 2. - Check the previous character
preorder.charAt(12) = '#', which is'#', no new slots created.
- Decrement
- i = 14:
preorder.charAt(14) = '#', not a comma, continue to the next character. - i = 15:
preorder.charAt(15) = ',', a comma is found.- Decrement
availableSlotsby 1:availableSlots = 1. - Check the previous character
preorder.charAt(14) = '#', which is'#', no new slots created.
- Decrement
- i = 0:
- Process the last node:
preorder.charAt(16) = '#', decrementavailableSlotsby 1:availableSlots = 0.
- Check final slot count:
availableSlotsis 0, so returntrue.
By following this step-by-step process, we verify that the serialization "5,2,#,#,3,1,#,#,#" is valid.
Code
Complexity Analysis
Time Complexity
- The algorithm iterates over each character in the input string exactly once. Therefore, the time complexity is
, where nis the length of the input string.
Space Complexity
- The space complexity is
since the algorithm only uses a fixed amount of extra space (i.e., a few variables like availableSlotsandlength) regardless of the size of the input string.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity